package practice1_100;

public class Practice518 {
    public int change(int amount, int[] coins) {
        int[] dp=new int[amount+1];
        dp[0]=0;
        for(int j=0;j<coins.length;j++){
            for(int i=1;i<dp.length;i++){
                if(coins[j]>i)continue;
                dp[i]=dp[i-coins[j]];
//                if(coins[j]<=amount&&i-coins[j]>=0) {
//                    if (dp[i - coins[j]] == 0)
//                        dp[i] = dp[i]+1;
//                    else dp[i] = Math.max(dp[i - coins[j]] , dp[i]);
//                }
            }
        }
        return dp[amount];
    }

    public static void main(String[] args) {
       int a= new Practice518().change(5,new int[]{1,2,5});
        System.out.println( a);
    }
}
